//
//  system.hpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/8/14.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef system_hpp
#define system_hpp

#include <stdio.h>

// 空闲让进、忙则等待、有限等待、让权等待

// ***** 信号量机制 *****
// 可以很好地解决进程互斥，进程同步的问题
// 用一对原语对信号量进行操作。信号量可以是整数，也可以是记录型
// wait(S)、signal(S)原语简称为P(S)、V(S)操作

// 整型信号量：只能进行初始化、P、V操作：
// 整型信号量不满足“让权等待”原则
/**
 int S = 1; // 初始化
 
 void P(S) { // P操作
    while (S <= 0);
    S--;
 }
 
 V(S){ // V操作
    S++;
 }
 
 P0进程：
 P(S);
 使用打印机;
 V(S);
 ...
 */

// 记录型信号量
// 可以解决盲等的问题
/**
 P(semaphore S) {
    S.value--;
    if (S.value < 0) { // 检查S.value = 打印机的数量
        block(S.L);
    }
 }
 
 V(semaphore S){
    S.value++;
    if (S.value <= 0) { // 检查S.value，如果归还打印机value == 0说明需要唤醒其他进程
        wakeup(S.L);
    }
 }
 */

// ***** 生产者 消费者 *****
// 互斥的P要放在同步的P之后
// 缓冲区没满V --empty--> P生产者生产
// 缓冲区非空V --full--> P消费者消费
/**
 semaphore mutex = 1;
 semaohore empty = n;
 semaphore full = 0;
 
 Producer
    生产一个产品
    P(empty);
    P(mutex);
    放入缓冲区
    V(mutex);
    V(full);
 
 Consumer
    P(full);
    P(mutex);
    消费一个产品;
    V(mutex);
    V(empty);
 */

// ***** 多生产者、多消费者 *****
// 这个例子中可以省略互斥信号量，但是如果盘子容量为2则不能省略。没时间分析可以加上互斥信号量
// 盘子为空 --plate--> 爸爸放苹果
// 盘子为空 --plate--> 妈妈放橘子
// 盘子有苹果 --apple--> 女儿吃
// 盘子有橘子 --orange--> 儿子吃
/**
 semaphore mutex = 1;
 semaphore plate = 1;
 semaphore apple = 0;
 semaphore orange = 0;
 
 Dad
 P(plate);
 放入苹果;
 V(apple);
 
 Mom
 P(plate);
 放入橘子;
 V(orange);
 
 Son
 P(apple);
 吃苹果;
 V(plate);
 
 Daughter
 P(orange);
 吃橘子;
 V(plate);
 */

// ***** 吸烟者问题 *****
// 请求桌子 --table--> 放材料
// 请求材料 --offer--> 卷烟
// ...

/**
 semaphore finish = 0;
 semaphore offer1 = 0;
 semaphore offer2 = 0;
 semaphore offer3 = 0;
 int i = 0;
 */

// ***** 读者 写者问题 *****
/**
 semaphore w = 1;
 semaphore rw = 1;
 semaphore mutex = 1;
 int count = 0;
 
 Writer
 P(w);
 P(rw);
 写入
 V(rw);
 V(w);
 
 Reader
 P(w);
 P(mutex);
 if (count == 0)
    P(rw);
 count++;
 V(mutex);
 V(w);
 读文件
 P(mutex);
 count--;
 if(count == 0)
    V(rw);
 V(mutex);
 */

// ***** 哲学家进餐问题 *****
/**
 semaphore chopsticks[5] = {1,1,1,1,1};
 
 P(mutex);
 P(chopsticks[i]);
 P(chopsticks[(i+1)%5]);
 V(mutex);
 吃饭
 V(chopsticks[i]);
 V(chopsticks[(i+1)%5]);
 */

// ***** 银行家算法 *****
// 1. 检查请求的数量是否超过最大需求
// 2. 检查请求的数量是否超过剩余
// 3. 预分配，判断是否安全
// 4. 根据3的结果确定是否分配资源

// *** 死锁的检测和解除 ***
// 1.互斥条件:只有对必须互斥使用的资源的争抢才会导致死锁(如哲学家的筷子、打印机设备)。
// 2.不剥夺条件:进程所获得的资源在未使用完之前，不能由 其他进程强行夺走，只能主动释放。
// 3.请求和保持条件:进程已经保持了至少一个资源，但又提出了新的资源请求，而该资源又被其他进程占有，
// 此时请求进程被阻塞，但又对自己已有的资源保持不放。
// 4.循环等待条件:存在一种进程资源的循环等待链，链中的 每一个进程已获得的资源同时被下一个进程所请求。

// ***** 内存基础知识 *****
// 什么是内存？有何作用？
// 比如8GB/64GB的手机，8GB为内存，64GB为外存。
// 内存用于存放数据，程序在执行之前需要把数据放入内存才能被CPU处理。-- 为了缓解CUP和硬盘的速度差
// 按字节编址，每个存储单元1b，8位
// 按字编址，每个单元16位（不一定）

// 4GB内存是什么意思？
// K 2^10
// M 2^20
// G 2^30
// 4GB = 2^32个字节，需要用32个二进制位表示(0 ~ 2^32-1)

// 指令工作的原理
// 源码x=x+1 --编译--> 机器指令 -> 放入内存PCB程序段、数据段 -> CPU读取指令处理
// 指令的工作基于地址
// 装入模块：可执行文件.exe
// 装入模块中的地址为逻辑地址（相对地址），除非从0开始装入内存，放入内存中无法找到正确的物理地址

// 如何将逻辑地址转为物理地址？
// 1. 绝对装入：编译器完成
// 在程序放入内存之前就知道从哪个位置放入（老旧的单道批处理时期使用，不灵活）
// 2. 静态重定位
// 装入模块装入内存时进行重定位，如从100开始装入内存，则所有地址+100（必须是连续的内存，全部装入内存，不可移动）
// 3. 动态重定位
// 需要重定位寄存器，记录了起始位置。CUP地址 = 逻辑地址 + 重定位寄存器(现代方法)

// 程序猿写代码 --编译-> 目标模块 --连接-> 装入模块 --装入-> 内存
// 如何连接？
// 1. 静态连接：程序运行前，连接各个模块形成装入模块
// 2. 装入时动态连接： 放入内存时才开始连接
// 3. 运行时动态连接：需要使用时才放入内存


// ***** 内存管理概念 *****
// 1. 内存空间的分配和回收
// 2. 内存逻辑扩充（虚拟技术）
// 3. 地址转换（三种装入方式）
// 4. 内存保护（各个进程使用独立的内存空间）
//  1.CPU设置上限寄存器 + 下限寄存器（物理地址上下限）
//  2.重定位寄存器和界地址寄存器（逻辑地址上限）

// ***** 覆盖与交换 *****
// 内存空间的扩充：
// 1. 覆盖技术：将程序分段，让常用段常驻内存。常用段放入固定区，不常用段放入覆盖区（需要调入调出）；
// 必须由程序员生命覆盖区，对用户不透明，增加编程负担。现在已经很少使用
// 2. 交换技术：进程在内存和磁盘间动态调度（中级调度）7状态模型，PCB不会换出内存
//  1. 放在外存的什么位置呢？：磁盘中有文件区（离散分配）和对换区（连续分配）。
//  2. 什么时候应该交换？内存不够用时
//  3. 换出什么进程？阻塞进程、优先级低的
// 覆盖技术和交换技术的区别：覆盖技术是在同一个程序或进程中进行的，交换技术是对于不同进程而言的。

// ***** 连续分配管理方式 *****
// 连续分配：系统为用户分配的必须是连续的内存空间

// 单一连续分配
// 内存被分配为系统区和用户区。内存中只有1道用户程序
// 优点：实现简单，无外部碎片，不一定需要内存保护
// 缺点：只能用于单用户、单任务的操作系统。有内部碎片

// 固定分区分配
// 把用户区划分为若干固定大小的分区，每个分区只能装入一道作业，进程之间互不干扰
// 分区大小相等：缺乏灵活性，适用于控制多个相同对象的场合
// 分区大小不等：增加灵活性
// 分区说明表：大小、起始位置、状态
// 优点：实现简单，无外部碎片
// 缺点：用户程序太大，需要采用覆盖技术，会产生内部碎片

// 动态分区分配
// 又称为可变分区分配，不会预先划分区域，根据进程的大小动态地建立分区
// 1. 用什么样的数据结构记录内存的使用情况？
// 空闲分区表：分区号、分区大小、起始地址、状态
// 空闲分区链：每个分区的起始部分和末尾部分，都会有一个指针指向前后的空闲分区
// 2. 当有多个空闲分区时，应该选择哪个分区分配？
// 按照动态分区分配算法
// 3. 如何进行分区的分配与回收？
// 分配：空闲分区表：修改分区大小、起始位置；如果正好全部分配，则删除一条记录
// 回收：空闲分区表：如果后面或前面有空闲分区，修改分区大小、起始位置；如果前后都有空闲分区，则合并；前后都没有空闲区，则新增。
// 内部碎片：分配给进程的资源，部分没有用上
// 外部碎片：内存中某些空闲分区太小而难以利用。通过紧凑（拼凑）技术来解决外部碎片。

// ***** 动态分区分配算法 *****
// 1. 首次适应算法（这个最好！）
// 按照空闲地址递增排序，通过顺序查找找到第一个满足的空闲分区
// 2. 最佳适应算法（算法开销大）
// 优先使用更小的分区。按照容量递增排序，顺序查找第一个满足的空闲分区；（保证大进程有足够空间）
// 缺点：会产生很多外部碎片。
// 3. 最坏适应算法（算法开销大）
// 优先使用更大的连续空闲区。
// 缺点：大进程可能没有足够大的分区分配
// 4. 邻近适应算法（对首次适应算法的优化）
// 按地址递增排列，从上次查找结束的位置开始

// 非连续存储
// ********** 分页存储管理 **********
// 什么是分页存储？（内存页框；进程页面）
// 将内存划分为大小相等的分区，每个分区为“页框”，页框编号从0开始
// 将进程的逻辑地址空间划分为与页框相同大小的部分，每个部分称为”页面“，页面编号从0开始
// 页面与页框有一一对应的关系，各个页面不需要连续存放

// 如何记录一一对应关系？
// 页表： 页号（进程的哪个页面），块号（存放到内存的哪个页框）
// 操作系统为每一个进程创建一个页表，保存在PCB中
// 1. 一个进程对应一张页表
// 2. 每个页面对应一个页表项

// 假设内存4GB，页面大小为4KB，则每个页表项应该为多少个字节？
// 页面=4KB=2^12B; 内存=4GB=2^32B; 页框=2^32/2^12=2^20; 块号范围0~2^20-1; 块号至少需要3B表示，页号不需要存储空间
// 进程如果有n个页面，页表需要3nB
// 页表起始地址为X，则页号为i的存放地址= X + 3 * i
// 块号=内存块号，而不是内存块的起始地址。起始地址=i * 页框大小

// 如何实现地址转换？
// 物理地址 = 页面在内存中的起始地址 + 逻辑地址（偏移量）
// 页号 = 逻辑地址 / 页面长度
// 页内偏移量 = 逻辑地址 % 页面长度
// 结论：页面大小为2^k，末尾k位表示偏移量，其余部分表示页号
// 如果页面大小为2^k，页表中的块号和偏移量拼接就能得到物理地址
// 如果k位表示页面偏移量，一个页面的大小是2^k内存单元
// 如果M位表示页号，说明一个进程最多能有2^M个页面

// ***** 基本地址变换机构 *****
// 页表寄存器PTR：页表在内存中的位置和页表长度；位置和长度在进程未执行时存放在PCB中
// 页面=2^10B,页号=2500/1024=2,偏移量=452
// 物理地址：2^10 * 8 + 452 = 2^13+452

// 页面 = 4kb=4*2^10=4096B
// 页表项 = 3B
// 1个页面可以存放4096/3=1365个页表项...1B内部碎片
// 1365号页表项地址：X + 3 * 1365 + 1
// 所以页表项拓展为4B可以方便地计算。
// 结论：实际中让每个页面能装下整数个页表项

// ***** 快表 *****
// TLB是高速缓存（不是内存），存放最近访问的页表项副本。页表称为慢表
// 基于局部性原理，快表命中率可以达到90%

// ***** 两级页表 *****
// 单级页表缺陷：
// 系统采用32位逻辑地址，页面大小为4KB=2^12B，页表项4B
// 页内地址为12位，剩余20位表示页号
// 一个用户进程最多有2^20页，页表中有2^20个页表项，一个页表占2^20*4B=2^22B
// 需要连续的页框：2^22 / 2^12 = 2^10

// 1. 当页表很大时，需要占用多个连续的页框。
// 建立一层”页目录表“
// 1个页面可以存放1K=2^10个页表项
// 可以把页表拆分为2^20/2^10=2^10=1024个小页表
// 小页表编号0,1,2...1023
// 页目录表：小页表编号 内存块号；通过页目录表可以找到二级页表的地址。
// 页目录表页表项：2^10
// 页目录表占用：2^12 需要连续的页框：1
// 32位表示法：(10位表示页目录表，10位表示二级页表，12位表示偏移量)

// 2. 进程在一段时间内只需要访问几个单独的页面。

// 注意：1. 若采用多级页表，各级页表的大小不能超过一个页面
// 例如：40位逻辑地址，页面大小4KB，页表项大小4B
// 页面大小=4KB=2^12B=页内地址大小
// 进程最多页面数：2^28
// 1个页面可以存放页表项：4KB / 4B = 1K = 2^10 = 1024
// 因此各级页表最多存储2^10个页表项，最多占10位
// 分级：(8位，10位，10位，12位)
// 3级页表，页内偏移为12位

// 2. 访存次数（假设没有快表）
// 单级页表需要进行2次访存：页表、目标
// 2级页表需要进行3次访存：页目录表、二级页表、目标
// n级页表访存次数=n+1次

// ***** 基本分段存储管理 *****
// 按照程序自身的逻辑关系划分为若干个段，每个段从0开始
// 每个段在内存中连续，但是段间不连续
// 逻辑地址：(段号，段内地址)
// 段号的位数决定了每个进程最多可以分几个段
// 段内地址位数决定了每个段最大长度

// 每个进程建立一张“段表”：（段号、段长、基址）

// ***** 分页和分段比较 *****
// 分页是系统行为，对用户不可见，为了实现离散分配，页的大小是固定的，一维
// 段是逻辑单位，对用户是可见的，为了满足用户需求，段长不定，二维

// 分段更容易实现信息的共享和保护（纯代码才可以共享）

// 分段需要2次访存（不引入快表时）

// ***** 段页式管理 *****
// 分页管理
// 优点：内存利用率高会产生少量的内部碎片，不会产生外部碎片
// 缺点：不容易实现信息的共享和保护
// 分段管理
// 优点：容易实现信息的保护
// 缺点：可能需要一大片连续的内存空间，会产生外部碎片

// 地址结构
// （段号，段内地址） --由系统自动分页-->（段号，页号，页面偏移量）
// 段号的位数决定了进程最多段数
// 页号位数决定了每个段最多有多少页面
// 页面偏移量决定了每个页面的大小

// 分段对用户是可见的，分页是不可见的，由操作系统完成
// 段页式是二维的

// 段表：段号、页号、偏移量
// 一个进程对应一个段表，多个页表
// 需要3次访存

// ***** 虚拟内存 *****

// 传统内存管理缺陷：
// 一次性：作业一次性装入内存后才开始运行，导致大作业无法运行，多作业并发度下降
// 驻留性：作业装入内存后，就会一直驻留
// 可以用虚拟技术解决！

// 局部性原理
// 时间局部性：如果执行了某条指令，不久后很有可能再次执行
// 空间局部性：如果访问了某个存储单元，不久后很可能访问附近的单元
// 高速缓存技术
// 1. 基于局部性原理，可以将程序即将使用的部分装入内存，暂时不用的留在外存。
// 2. 当访问的信息不在内存中时，操作系统将所需信息从外存中调入
// 3. 当内存不够用时，把暂时不用的信息放入外存

// 虚拟性特征
// 多次性：允许作业多次放入内存
// 对换性：允许作业换入换出
// 虚拟性：用户看到的容量比实际容量要大

// 如何实现？
// 如果采用连续分配，会不方便实现，因此虚拟技术需要离散分配
// 操作系统功能：（放入内存）请求调页（调段）、（放入外存）页面置换（段置换）

// ***** 请求分页管理方式 *****

// 请求分页与基本分页的区别
// 当访问的信息不在内存，操作系统负责将信息调入内存
// 当内存空间不够时，将暂时不使用的信息调出内存

// 页表
// 请求分页：页号，内存块号，状态位，访问字段，修改位，外存地址
// 基本分页：页号、内存块号

// 缺页中断机构
// 当访问的页面不存在时，产生一个缺页中断，进程阻塞，调页完成后唤醒
// 如果内存中有空闲块，则为进程分配一个内存块，并修改页表
// 如果内存中没有空闲块，则由页面置换算法选择一个页面淘汰，若该页面被修改过，则写回外存
// 缺页中断属于内中断
// 一条指令可能产生多次缺页中断

// ***** 页面置换算法 *****

// 1. 最佳置换法（OPT）（需要提前知道以后要访问的页面，理想化的算法）
// 每次选择在最长时间内不再被使访问的页面
// 注意：缺页中断不一定发生页面置换，只有在内存满时发生缺页中断才发生页面置换
// 缺页率：访问次数 / 缺页中断
// 最理想

// 2. 先进先出（FIFO）
// 淘汰最早进入的页面
// Belady异常--为进程分配的物理块越多，缺页次数反而越多
// 性能差

// 3. 最近最久未使用算法（LRU）
// 淘汰最近最久未访问的页面
// 访问字段记录上次访问以来所经历的时间t
// 需要特殊硬件支持，性能好，开销大，实现困难

// 4. 时钟置换算法（CLOCK）最近未用法（NRU）
// 页表中访问位1表示最近使用过，0表示最近未使用

// 5. 改进型时钟置换算法
// 淘汰访问位为0的页面；像一个时钟不断转圈
// 第一轮扫描找访问位为0的页面，扫描页面后将访问位修改为0
// 第二轮扫描继续找访问位为0的页面
// 算法开销小，性能不错

// 改进：优先淘汰没有被修改过的页面；增加一个修改位(访问位，修改位)
// 第一轮扫描找(0,0)，不修改任何标志位
// 第二轮扫描找(0,1)，访问位修改为0
// 第三轮扫描找(0,0)，不修改任何标志位
// 第四轮扫描找(0,1)，不修改任何标志位

// ***** 页面分配策略 *****

// 驻留集：请求分页存储管理中分配给进程的物理块集合；采用虚拟技术，驻留集一般小于进程总大小
// 驻留集太小，频繁缺页；驻留集太大，并发度下降。
// 固定分配：驻留集不变
// 可变分配：驻留集可变
// 局部置换：发生缺页时只能使用进程自己的物理块置换
// 全局置换：可将系统空闲的物理块分配给进程，也可以把其他进程的物理块先置换到外存，再分配给进程

// *****
// 局部置换+固定分配：灵活性低，很难确定分配多少固定的内存
// 全局置换+可变分配：只要缺页就分配空闲物理块，会导致驻留集过大
// 局部置换+可变分配：如果频繁缺页时才给进程分配，如果缺页率低，则会减少进程物理块

// 1.预调页策略
// 预测即将使用的页面，一次性调入内存中，I/O开销小；如果调入的页面未使用则会造成低效；
// 主要用于首次调用，由程序员指出需要调入的页面

// 2.请求调页策略
// 运行时发现缺页才调入，每次调入1个页面，I/O开销大

// 1. 系统有足够空间时，内存在对换区中调入调出
// 2. 系统没有足够的空间，不被修改的数据从文件区调入
// 3. UNIX方式：第一次使用时，全部数据全部放入文件区；调出时放入对换区。

// *** 抖动（颠簸）现象 ***
// 换出立马调入；调入立马换出。（低效）
// 说明分配给进程的物理块不够

// 驻留集：请求分页中分配给进程的物理块集合。
// 工作集：某段时间里，实际访问页面的集合。
// 窗口尺寸：工作集可能小于窗口尺寸。
// 驻留集应该大于工作集，否则会频繁缺页。


// ***** 初识文件管理 *****

// 文件属性
// 1. 文件名：同一个目录下不允许有重名文件
// 2. 标识符：文件唯一标识符
// 3. 类型
// 4. 位置：存放路径、外存地址
// 5. 大小
// 6. 创建 / 修改 / 打开时间
// 7. 保护信息：设置读写权限

// 文件内部的组织
// 无结构文件：二进制、字符流
// 有结构文件：由一条条记录组成；记录由数据项组成

// 文件之间的组织
// 树状组织（一层一层目录）
// 目录也是有结构的文件

// 系统向上层提供的功能
// 新建文件夹，新建文件，双击打开文件，修改文件，删除文件
// 系统调用：create\read\write\delete\open\close

// ***** 文件的逻辑结构 *****

// 有结构文件 Excel
// 由一条条记录组成；记录由数据项组成
// 每条记录中有一个数据项作为关键字

// 定长记录：每条记录长度相同
// 可变长记录：每条记录长度不同（常用）

// 顺序文件（默认为物理上顺序存储的文件）
// 记录在逻辑上是顺序的；在物理上可以是连续存储或者链式存储
// 记录是定长或可变长度的
// 链式存储：无论是定长还是可变长记录，都必须遍历
// 顺序存储：可变长记录必须遍历
// 顺序存储：定长记录可以随机存取，关键字排序可以实现折半查找
// 顺序文件增加/删除记录困难。

// 索引文件
// 让记录不用保持顺序，方便增加/删除。
// 索引表（索引号、长度、指针）（索引表本身就是定长顺序文件）
// 一个记录对应一条索引
// 按关键字顺序排列可以支持折半查找，及时性高

// 索引顺序文件
// 一组记录对应一个索引表项
// 解决了索引表可能大于文件大小
// 如果记录过多，可以使用多级索引...

// ***** 文件目录 *****

/**
 ~ # ls -al
 drwxrwxr-x+ 72 root  admin  2304  8 13 17:39 Applications
 drwxr-xr-x  67 root  wheel  2144  8 12 10:22 Library
 drwxr-xr-x@  8 root  wheel   256  9 30  2019 System
 drwxr-xr-x   5 root  admin   160  9 30  2019 Users
 drwxr-xr-x   3 root  wheel    96  8 21 11:45 Volumes
 drwxr-xr-x@ 38 root  wheel  1216  6 28 17:39 bin
 drwxr-xr-x   2 root  wheel    64  8 25  2019 cores
 dr-xr-xr-x   3 root  wheel  4360  8 21 08:42 dev
 */

// 文件控制块（File Control Block）
// FCB：（文件名、类型、权限、...物理地址）
// 文件目录：FCB的有序集合（FCB是目录项）

// 目录的功能：（增删改查）
// 搜索：搜索目录找到文件
// 创建文件：在目录中新增
// 删除文件：在目录中删除
// 显示目录：目录的属性（显示文件数量）
// 修改目录：文件修改时，目录也需要修改

// 1.单级目录结构
// 操作系统只有一张目录表，文件不允许重名
// 不是适用多用户系统

// 2.两级目录结构
// 主文件目录+用户文件目录
// 允许不同用户的文件重名；可以控制权限；
// 用户无法对文件分类

// 3.多级目录结构（树形目录结构）
// 不同目录下的文件可以重名，各级目录间用"/"隔开
// 从根目录出发称为绝对路径
// /照片/2020-01-01/自拍.jpg：需要3次磁盘I/O
// 从当前目录出发称为”相对路径“，I/O次数可以减少
// *** 不便于实现文件的共享 ***

// 4.无环图目录结构（有向无环图）
// 可以用不同的文件名指向同一个文件，实现多个用户的文件共享
// 删除共享文件时，如果文件被其他用户共享，则不能直接删除文件；设置文件计数器，记录用户数量。计数器为0时才删除

// 索引结点（给FCB瘦身）
// （文件名，索引结点指针） 指针指向索引结点，存放除了文件名之外的信息
// 如：FCB占64B，一个磁盘块1KB；一个磁盘块最多16个FCB，如果文件目录中有640个目录项，则需要40个磁盘块保存
// 平均查找320个目录项，平均I/O：320/16 = 20次
// 采用索引结点：16B，一块磁盘最多64个，需要10个磁盘块保存
// 平均查找320个目录项，平均I/O：320/64 = 5次

// ***** 文件的物理结构 *****

// 文件块、磁盘块
// 文件被分为一个一个的块，文件的逻辑地址（逻辑块号，块内地址）

// 连续分配
// 每个文件在磁盘上占用连续的块
// 文件目录中需要记录：起始块号和长度（通过长度验证逻辑块号是否合法）
// 优点
// 1. 支持随机访问
// 2. 访问磁盘块时，需要移动磁头，两个磁盘块相距越远，移动所需时间越长；因此连续分配读写时间最短。
// 缺点
// 1. 不方便拓展
// 2. 存储空间利用率低，会产生难以利用的磁盘碎片

// 链接分配
// 文件是离散的

// 隐式链接（默认）
// 链式存储
// 文件目录中记录起始块号和结束块号；访问i号逻辑块，需要i+1次I/O
// 不支持随机访问；拓展方便；不会有磁盘碎片

// 显式链接
// 链式存储，将物理块指针存放到一张表中（FAT文件分配表）
// 一个磁盘只需要一张FAT，开机时常驻内存
// 文件目录中只需记录起始块号
// 优点：
// 支持随机访问，不需要访问磁盘，不会产生外部碎片
// 缺点：
// FAT占用一定的内存

// 索引分配
// 系统为每个文件建立索引表记录文件的逻辑块对应的物理块（逻辑块号（隐藏），物理块号）
// 目录中记录索引块地址
// 索引块：存放索引表的磁盘块
// 数据块：存放文件内容的磁盘块
// 优点：支持随机访问，文件拓展方便
// 缺点：占用一定的存储空间

// 如果索引表太大，一个磁盘块放不下时
// 1. 链接方案
// 索引块增加指针指向下一块
// 目录只需要记录第一块索引块地址
// 假设磁盘块大小为1KB，索引项占4B，则一个磁盘块可以存放256个索引项
// 若一个文件大小为64MB，64*2^20=2^26B;
// 文件占磁盘块：2^26 / 2^10 = 2^16块
// 索引表占磁盘块：2^16 / 2^8 = 2^8 = 256块
// 找到最后一个索引块，I/O次数高，效率低

// 2. 多层索引
// 各层索引表大小不能超过1个磁盘块
// 假设磁盘块大小为1KB，索引项占4B，则一个磁盘块可以存放256个索引项
// 2层索引存放256*256=2^16个文件块，最大文件大小：2^16 * 2^10 = 2^26 = 64MB;3次I/O
// 3层索引：256*256*256*2^10= 2^34=16GB；4次I/O
// 缺点：如果文件很小，也需要3次I/O

// 3. 混合索引
// x个直接地址，y个一级索引，z个二级索引
// 最大文件块数：x + y*256 + z*256*256

// ***** 逻辑结构&&物理结构 *****
// 一个文件，在用户的视角来看是连续的（逻辑）
// 在系统的视角里，就是一堆二进制，会被拆分为若干文件块（物理）

// ***** 文件存储空间管理 *****

// 文件卷（逻辑卷，逻辑盘）：把磁盘分为C盘、D盘...
// 文件卷又划分为：目录区和文件区
// 目录区：存放目录信息FCB、空间管理信息
// 文件区：存放文件数据
// 超大型文件，可把多个磁盘组成一个文件卷

// 空闲表法
// （第一个空闲地址，空闲块数）
// 适用于文件物理结构是连续分配的
// 分配：可以采用首次适应、最佳适应、最坏适应等算法分配空间
// 回收：注意合并问题

// 空闲链表法
// 空闲盘块链
// 系统保存空闲的链头和链尾；链头 --> 链尾
// 分配：从链头拆下n个盘块进行分配
// 回收：回收的盘块挂到链尾
// 适用于离散分配的物理结构，1个文件分配多个磁盘块时效率低

// 空闲盘区链
// 系统保存链头、链尾指针
// 分配：首次适应，最佳适应等进行分配；如果文件太大，可以分配多个盘区
// 回收：注意回收时合并的问题
// 适用于离散和连续分配。1个文件分配多个磁盘块时效率高

// *** 位示图法 ***
// 位示图：0代表空闲，1代表分配
// (字号，位号)和盘块号的转换
// 分配：找到n个”0“，设置为“1”
// 回收：设置为”0“
// 适用离散分配和连续分配

// 成组链接法
// 文件卷中的目录区设置一个”超级块“，开机时读入内存，并保持一致
// 超级块：下一组空闲盘块数量，下一组空闲盘块号
// 下一组空闲盘的第一块，记录了下一组空闲盘块数量和下一组空闲盘块号...
// 导数第二组的第一个盘块中的下一组盘块号的第一个设为-1，表示下一组没有后续了。

// 每一组的盘块数量有上限；最后一组的盘块数比其他组少1
// 分配
// 检查第一个分组的数量是否足够；
// 若足够，则修改分组数量，分配盘块；
// 若正好为100块，把下一组的第一块复制到超级块中；
// 若不足，也需要把后面的第一块复制到超级块中。

// 回收
// 若超级块没满，修改超级块中的数量，增加链接
// 若满了，则把超级块复制给下一块，超级块指向下一块

// ***** 文件的基本操作 *****
// 创建文件
// 1. 为文件分配存储空间
// 2. 创建目录项

// 删除文件
// 1. 找到目录项
// 2. 回收磁盘块
// 3. 删除目录项

// 打开文件
// 1. 找到目录项，检查用户权限
// 2. 将目录项复制到打开文件表中，返回打开文件编号，通过编号操作文件（又称为文件描述符）
// 系统打开文件表：整个系统只有一张，记录了所有打开的文件（用打开计数器来记录有多少进程打开了文件）
// 进程A的打开文件表：记录进程打开的文件（读写指针：进程操作到了什么位置；访问权限；系统索引表号）

// 关闭文件
// 1. 删除进程的打开文件表
// 2. 回收资源
// 3. 系统打开文件表的打开计数器-1

// 读文件
// 指明读哪个文件（打开文件的编号、文件描述符）
// 指明读多少数据：KB
// 指明数据放在内存的哪个位置

// 写文件
// 指明写哪个文件
// 写多少数据
// 写的数据存放在内存中的位置

// ***** 文件共享 *****
// 硬连接：基于索引结点的共享
// 多个目录项的索引指针，指向同一个索引结点；索引计数器记录被指的次数
// 删除文件时，若索引计数器大于0，则只删除指针；

// 软连接：基于符号链的共享方式
// 目录项指向link文件，link文件中记录了文件路径，进而找到真实的索引结点
// 类似于Windows中的快捷方式
// 若”真实“文件被删除，则软连接失效
// 需要一层一层地找文件

// ***** 文件保护 *****
// 口令保护
// 设置口令后，用户访问必须提供“口令”
// 口令存储在FCB或索引结点中
// 优点：开销小
// 缺点：口令存放在系统内部，不够安全

// 加密保护
// 最简单的加密：异或加密
// 系统中保存的是加密后的数据
// 优点：密码不在系统中，保密性强
// 缺点：加密/解密需要一定的开销

// 访问控制
// 在FCB或索引结点中添加访问控制表
// 系统对比用户是否有相应的权限
// 如果系统中有很多用户，则访问控制表会很庞大；可以使用分组来解决（精简的访问控制列表）

// ***** 文件系统的层次结构 *****
// 用户接口：Read、Write、Open、Close...
// 文件目录系统：通过路径找到FCB或索引结点、管理打开文件表
// 存取控制块：文件保护
// 逻辑文件系统与文件信息缓冲区：文件中的记录号转换为逻辑地址；索引表调入文件信息缓冲区
// 物理文件系统：逻辑地址转换为物理地址
// 辅助分配模块：分配、回收、
// 设备模块：硬件

// 用例子辅助记忆

// ***** 文件管理实例 *****
// 某个操作系统的管理：
// 1. 文件物理结构：混合索引
// 2. 文件目录：索引结点
// 3. 空闲分区管理：位示图

// ***** 磁盘的物理结构 *****

// 磁道：一圈一圈的叫做磁道

// 扇区：每个磁道被划分为扇区，每个扇区存放的数据量相同（磁盘块）
// 扇区可以编号；最内侧的扇区面积最小，数据密度最大

// 盘面：磁盘中有很多个盘面，每个盘面都有一个磁头
// 盘面可以编号；一个盘片可以对应2个盘面
// 所有的磁头只能共进退

// 柱面：所有盘面上相对位置相同的磁道，组成了柱面
// 可以用（柱面号，盘面号，扇区号）表示所有磁盘块
// 1. 根据柱面号移动磁臂，让磁头移动到指定柱面
// 2. 激活指定盘面的磁头
// 3. 磁盘旋转的过程中，指定的扇区会从磁头下划过，这样就完成了对指定扇区的读/写

// 磁盘分类
// 活动头磁盘：磁臂带动磁头定位磁道
// 固定头磁盘：每个磁道都对应一个磁头
// 可换盘磁盘/固定盘磁盘

// ***** 磁盘调度算法 *****

// 寻道时间：磁头的移动需要花费一定的时间
// 1. 启动磁头臂：S时间
// 2. 移动磁头：移动一个磁道需要m时间
// 移动n个磁道：Ts = S + m * n

// 延迟时间：磁头定位到指定扇区的时间
// 设磁盘的转速r 转/秒
// 平均延迟时间：转1圈需要1/r，平均需要转半圈
// Tr = 1 / (2r)

// 传输时间
// 假设转速为r转/秒，需要读写b字节，每个磁道保存N字节
// 读写一个磁道所需时间：1/r
// Tt = (1/r) * (b/N)

// 延迟时间和传输时间和磁盘的转速线性相关，所以操作系统无法优化
// 只有寻道时间可以被优化

// 先来先服务算法FCFS
// 根据进程请求访问磁盘的先后顺序进行调度
// 磁头的初始磁道是100、分别移动到55、58、39、18、90、160、 150、38、184
// 总共移动45+3+19+21+72+70+10+112+146=498个磁道
// 平均移动：498/9=55.3
// 优点：公平，如果请求的磁道集中，性能还行
// 缺点：如果大量进程请求分散的磁道，性能差

// 最短时间优先SSTF
// 贪心算法，只选择眼前最优的
// 磁头的初始磁道是100、分别移动到18、38、39、55、58、90、150、160、184
// 总共移动：10+32+3+16+1+20+132+10+24=248个磁道
// 平均移动：248/9=27.5
// 优点：性能较好
// 缺点：有可能产生饥饿

// 扫描算法SCAN
// 电梯算法
// SSTF算法导致饥饿是因为磁头可能在一小块区域内来回移动。
// 规定：只有移动到最外侧时才能向内移动，只有移动到最内侧时才能向外移动。
// 就算最外侧没有数据需要被访问，也需要移动到最外侧
// 优点：性能较好，不会产生饥饿
// 缺点：
// 1.必须要移动到最外侧
// LOOK算法：如果移动方向上，没有数据需要访问了，则立刻回头
// 2.各个磁道的访问频率不平均
// C-SCAN算法：只有磁头朝某个方向移动时才访问数据；返回时快速直接回到起始侧
// C-SCAN缺点：外侧没有数据需要访问，还会继续移动到外侧；返回时，直接返回到0
// C-LOOK算法：磁头不一定需要移动到最外侧；磁头返回时，返回内侧有数据的磁道上

// ***** 减少磁盘延迟时间的方法 *****
// 磁头读取一块扇区后，需要一定的时间准备才能继续读入扇区
// 所以物理上相邻的扇区，需要较长的“延迟时间”

// 交替编号（一块盘面上）
// 让逻辑上相邻的扇区，在物理上分隔

// 磁盘的物理地址：（柱面号，盘面号，扇区号）
// 为啥不能是（盘面号，柱面好，扇区号）？
// 读取连续的磁盘块时，可以减少磁头移动的时间

// 错位命名（相反的盘面）
// (000,00,111)访问下一个(000,01,000)时，他们的位置是相邻的；磁盘无法一次读取连续的扇区，需要多转一圈
// 不同的盘面，相对位置的编号错位可以减少延迟时间

// ***** 磁盘的管理 *****

// 磁盘初始化
// 1.（出厂前）物理格式化：划分扇区
// 扇区可以分为：头、尾、数据区域
// 2.将磁盘分区：每个分区由若干柱面组成（C盘、D盘...）
// 3.逻辑格式化，创建文件系统：包括根目录文件，存储空间管理数据结构（位示图，空闲分区表等）

// 引导块
// ROM中存放“自举装入程序”（主板中的只读模块）
// 通过“自举装入程序”可以找到磁盘的引导块（启动块/启动分区），将完整的“自举程序”读入内存，完成开机初始化
// 拥有引导块（启动分区/启动块）的磁盘称为系统磁盘：例如C盘

// 坏块的管理
// 标记坏掉的扇区，如在FAT中标明（对操作系统不透明）
// 保留一些“备用扇区”来替换扇区（对操作系统透明）
// 对于复杂的磁盘，会维护一个坏块表


// ***** 设备管理 *****
// I/O设备：外部设备，“输入” 和 “输出”
// UNIX系统将外部设备抽象为特殊的文件，Write输出，Read写入

// 人际交互类：鼠标、键盘、打印机 （慢）
// 存储设备：移动硬盘（快）
// 网络通信设备：路由器（中）

// 块设备：传输速度快，可寻址（移动硬盘）
// 字符设备：传输速度慢，不可寻址，常采用中断驱动方式（鼠标键盘）

// ***** I/O控制器 *****
// I/O设备由机械部件和电子部件组成
// 机械部件：看得见摸得着

// 电子部件（I/O控制器）：印刷电路板；CPU控制I/O机械部件的”中介“
// 1. 接收和识别CUP命令，设置控制寄存器来存放命令和参数
// 2. 向CPU报告设备的状态，设置状态寄存器（1空闲，0忙碌等）
// 3. 数据交换，设置数据寄存器暂存输入输出的数据
// 4. 地址识别，类似于内存地址，为了区分各个寄存器的地址
// 1个I/O控制器可能对应多个设备
// 数据寄存器，控制寄存器，状态寄存器可能有多个

// I/O控制器的组成
// CUP与控制器的接口（实现与CUP的通信）
// I/O逻辑（识别CUP的命令，向设备发送命令）
// 控制器与设备的接口（实现与设备的通信）

// 内存印象I/O
// 控制器的的寄存器与内存统一编址
// 优点：简化指令

// 寄存器独立编址
// 与内存不统一。
// 缺点：需要设置专门的指令实现对控制器的操作

// ***** I/O的控制方式 *****

// *** 程序直接控制方式（关键词：轮询）
// 1.流程
// 2.CUP干预频率：
// I/O开始的前后都需要CUP介入，等待时还需要不断轮询
// 3.传输的单位：1个字
// 4.数据流向
// 读操作：I/O设备 -> CUP -> 内存
// 写操作：内存 -> CUP -> I/O设备
// 5.优点：实现简单
// 缺点：CUP和I/O只能串行工作，CUP等待时会处于”忙等“状态，CUP利用率低

// *** 中断驱动
// 1.流程在程序直接控制中引入中断
// 2.CUP干预：I/O前后进行干预
// 3.传输单位1个字
// 4.数据流向：同程序直接控制
// 5.优点：CUP和I/O可以并行工作，不需要轮询，CUP利用率提升
// 缺点：每次只能传输1个字，中断频繁会影响性能
// CUP会在指令末尾检查中断
// 处理中断需要保存和恢复运行环境，如果中断频繁会影响性能
// 每次只能读入一个字

// *** DMA方式（Direct Memory Access：直接存储器存取）
// 主要用于块设备的I/O控制（DMA控制器）
// 数据传输单位“块”（读写多个块时，只能是连续的块，并且这些块存入内存也必须是连续的）
// 数据可以直接从设备到内存，从内存到设备
// CUP仅仅在开始或者结束时才进行干预，数据的读写不再经过CUP
// 数据的流向：I/O设备 <--> 内存
// 优点：数据以块为单位；CUP介入频率低；数据直接从I/O设备到内存；CUP利用率高
// 缺点：一次只能读写1块或者连续的块

// *** 通道控制方式
// 通道：硬件（弱鸡版的CUP），可以识别和执行一系列的通道指令
// 1. CUP向通道指明通道程序的地址和需要操作哪些I/O设备
// 2. 通道执行通道程序（指明读入和写出多少数据和对应的地址）
// 3. 通道执行完毕后，执行中断指令
// CUP干预：极低
// 每次可以读写一组数据块
// 数据的流向：I/O设备 <--> 内存
// 优点：CUP，通道，I/O设备可以并行工作，资源利用率高
// 缺点：实现复杂

// ***** I/O软件结构 *****

// 层次（记住顺序即可）
// 1.用户层软件
// 与用户交互，用户可以直接使用库函数进行IO操作（系统调用）
// 2.设备独立性软件
// 又称为设备无关性软件；实现与设备硬件无关的功能
//  1.向上层提供系统调用（Read、Write）
//  2.设备的保护（权限）
//  3.差错处理
//  4.设备的分配与回收
//  5.数据缓冲区管理
//  6.建立逻辑设备名到物理设备名的映射关系；根据不同的设备调用相应的驱动程序
// 3.设备驱动程序（和硬件有关）
// 4.中断处理程序（和硬件有关）
// 5.硬件
// 每一层都是对上一层的封装
// 2，3，4属于内核既“IO系统”

// ***** I/O核心子系统 *****

// 设备独立层
// I/O调度
// 如：磁盘调度算法、打印机调度算法

// 设备独立层
// 设备保护
// 设备被看作特殊的文件，系统会为这些文件建立FCB从而验证用户的访问权限

// ***** 假脱机技术 *****
// 脱机技术：脱离主机进行”输入“和“输出”
// SPOOLING技术：使用软件方式模拟脱机技术（需要并发）
// 输入井/输出井：模拟磁带
// 输入进程和输出进程：模拟外围控制机

// 共享打印机

// ***** 设备的分配与回收 *****
// 设备分配
// 设备的固有属性：独占设备（打印机）、共享设备（磁盘）、虚拟设备（SPOOLING技术）
// 设备的分配算法：先来先服务、短任务优先...
// 设备分配的安全性：
// 安全分配：进程分配设备后阻塞等待，直到I/O完成时唤醒
// 优点：破坏了“请求和保持”条件不会产生死锁
// 缺点：CUP和I/O只能串行工作

// 不安全分配：直到某个I/O请求不满足时才阻塞
// 优点：效率高
// 缺点：可能发生死锁

// 静态分配：运行前必须分配全部资源，破坏了“请求和等待”条件
// 动态分配：运行过程中动态申请资源

// 设备控制表（DCT）
// 每个设备都有一张DCT，记录设备的情况
// 控制器控制表
// 通道控制表
// 系统设备表...

// ***** 缓冲区管理 *****
// 缓冲区：可以由硬件寄存器组成，也可以由内存组成
// （硬件缓冲区造价高，容量小）

// 作用：可以缓和CUP和I/O设备的速度差
// 可以减少CPU的中断频率
// 解决数据粒度不匹配的问题
// 提高CPU和I/O设备的并行性

// 单缓冲（工作区满，缓冲区空）
// 技巧：假定一个状态，分析下次到达这个状态需要多少时间，这个时间就是处理一块数据的平均时间
// max(C,T)+M

// 双缓冲（工作区空，只有一个缓冲区满）
// max(T,C+M)

// ”管道“就是缓冲区

// 循环缓冲区
// 缓冲池

#endif /* system_hpp */
